import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 面试题 17.14. 最小K个数
 * https://leetcode-cn.com/problems/smallest-k-lcci/
 */
public class Solutions_mianshi_17_14 {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 2, 4, 6, 8};
//        int k = 4;  // output:{1, 2, 3, 4}
        int k = 8;  // output:{1, 2, 3, 4, 5, 6, 7, 8}

//        int[] arr = {1, 2, 3};
//        int k = 0;  // output:{}

        int[] result = smallestK(arr, k);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解法三：快速排序（2ms）
     * TopK 排序
     */
    public static int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        quickSort(arr, 0, arr.length - 1, k);
        return Arrays.copyOf(arr, k);
    }

    private static void quickSort(int[] arr, int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int cl = left, cr = right;
        int value = arr[left];
        int i = left;

        while (i <= cr) {
            int j = arr[i];
            if (j > value) {
                swap(arr, i, cr);
                cr --;
            } else if (j < value) {
                swap(arr, i, cl);
                cl ++;
                i ++;
            } else {
                i ++;
            }
        }
        // 排序后，[left, cr] 中的元素，都小于等于 [cr + 1, right] 中的元素
        // 已排序的元素个数
        int count = cr - left + 1;
        if (count >= k) {
            // 左半部分排序
            quickSort(arr, left, cl - 1, k);
        } else {
            // 右半部分排序
            quickSort(arr, cr + 1, right, k - count);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 解法二：Arrays.sort（7ms）
     */
    public static int[] smallestK3(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        Arrays.sort(arr);
        return Arrays.copyOf(arr, k);
    }

    /**
     * 解法一：优先队列（31ms）
     */
    public static int[] smallestK2(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        // 堆顶元素为较大值
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o2, o1);
            }
        });
        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < queue.peek()) {
                queue.poll();
                queue.offer(arr[i]);
            }
//            queue.offer(arr[i]);
//            if (queue.size() > k) {
//                queue.poll();
//            }
        }

        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = queue.poll();
        }
        return res;
    }
}
